package com.fw.structure.sparsearray;

import lombok.extern.slf4j.Slf4j;

/**
 * @Author:yanwei
 * @Date: 2020/10/23 - 23:45
 * <p>
 * 稀疏数组的实现，结构
 */
@Slf4j
public class Sparsearray {

    /**
     * 棋盘案例
     *
     * @param args
     */
    public static void main(String[] args) {
        //1 创建一个 棋盘为 row = 11 col = 11 的盘局
        int chessArr[][] = new int[11][11]; // 11 行，11列
        //2. 模拟当前 第一行第6列有一个 白子，第10行第5列有一个黑子
        //0 = 空盘，1 = 白子，2 = 黑子
        chessArr[0][5] = 1;
        chessArr[9][4] = 2;
        chessArr[9][5] = 2;
        chessArr[10][5] = 2;
        chessArr[7][5] = 2;
        for (int[] ints : chessArr) {
            for (int anInt : ints) {
                System.out.printf("%d\t", anInt);
            }
            System.out.println();
        }
        /**
         * 转为稀疏数组
         *
         * 1. 得到所有不为 0 的有值的数据
         * 2. 将有值的数据作为 个数 累加
         * 3. [0][0]稀疏数组第一行存入 原始的 行列，以及有数据的个数
         * 4. 其它行记录 值 存在了那行，那一列
         */
        int sum = 0;
        for (int[] chessS : chessArr) {
            for (int chessVal : chessS) {
                if (chessVal != 0) {
                    sum++;
                }
            }
        }
        // 此处是在棋盘案列中是固定的，因为第一行需要记录  原始数组的行列，以及有值的个数
        // 整好 3 列进行记录
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = chessArr[0].length;
        sparseArr[0][1] = chessArr[0].length;
        sparseArr[0][2] = sum;
        // 第一行数据准备就绪

        // 接下来进行填充数据
        int count = 0;

        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[i].length; j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                }
            }
        }
        // 至此，稀疏数组填充完毕
        for (int[] ints : sparseArr) {
            for (int anInt : ints) {
                System.out.printf("%d\t", anInt);
            }
            System.out.println();
        }
        /**
         * 稀疏 数组 恢复为原始数组
         * 1. 第一行记录了 行，列，值
         * 2. 遍历初始化的原始数组，和 稀疏数组做对比进行填充
         */
        chessArr = new int[sparseArr[0][0]][sparseArr[0][1]];
        // 得到个数的数量
        sum = sparseArr[0][2];
        for (int i = 1; i < sparseArr.length; i++) {
           lab: for (int j =  0; j <sparseArr[i].length; j++) {
                // 得到行
               int row  = sparseArr[i][j];
                // 得到列
               int col = sparseArr[i][j+1];
                //得到值
               int value =  sparseArr[i][j+2];
               chessArr[row][col] = value;
                break lab;
            }
        }
       // 编列转化后的
        for (int[] ints : chessArr) {
            for (int anInt : ints) {
                System.out.printf("%d\t", anInt);
            }
            System.out.println();
        }
    }
}
